﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0040)http://en.wikipedia.org/wiki/Algorithm_X -->
<HTML lang=en dir=ltr xml:lang="en" 
xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>Knuth's Algorithm X - Wikipedia, the free encyclopedia</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META http-equiv=Content-Style-Type content=text/css>
<META content="MSHTML 6.00.2900.5897" name=GENERATOR><LINK 
href="/wiki/Knuth%27s_Algorithm_X" rel=canonical><LINK title="Edit this page" 
href="/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit" 
type=application/x-wiki rel=alternate><LINK title="Edit this page" 
href="/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit" rel=edit><LINK 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/combined.min.css" 
type=text/css rel=stylesheet><LINK 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/jquery-ui-1.7.2.css" 
type=text/css rel=stylesheet><LINK 
href="http://en.wikipedia.org/apple-touch-icon.png" rel=apple-touch-icon><LINK 
href="/favicon.ico" rel="shortcut icon"><LINK title="Wikipedia (en)" 
href="/w/opensearch_desc.php" type=application/opensearchdescription+xml 
rel=search><LINK href="http://creativecommons.org/licenses/by-sa/3.0/" 
rel=copyright><LINK title="Wikipedia RSS Feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=rss" 
type=application/rss+xml rel=alternate><LINK title="Wikipedia Atom Feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=atom" 
type=application/atom+xml rel=alternate><LINK media=screen 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/shared.css" 
type=text/css rel=stylesheet><LINK media=print 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/commonPrint.css" 
type=text/css rel=stylesheet><LINK media=screen 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/main.css" 
type=text/css rel=stylesheet><LINK media=handheld 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Knuth's Algorithm X - Wikipedia, the free encyclopedia.files\main(1).css" 
type=text/css rel=stylesheet><!--[if lt IE 5.5000]><link rel="stylesheet" href="/skins-1.5/monobook/IE50Fixes.css?257z2" type="text/css" media="screen" /><![endif]--><!--[if IE 5.5000]><link rel="stylesheet" href="/skins-1.5/monobook/IE55Fixes.css?257z2" type="text/css" media="screen" /><![endif]--><!--[if IE 6]><LINK 
media=screen 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/IE60Fixes.css" 
type=text/css rel=stylesheet><![endif]--><!--[if IE 7]><link rel="stylesheet" href="/skins-1.5/monobook/IE70Fixes.css?257z2" type="text/css" media="screen" /><![endif]--><LINK 
media=all 
href="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/index.css" 
type=text/css rel=stylesheet><LINK media=print 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Knuth's Algorithm X - Wikipedia, the free encyclopedia.files\index(1).css" 
type=text/css rel=stylesheet><LINK media=handheld 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Knuth's Algorithm X - Wikipedia, the free encyclopedia.files\index(2).css" 
type=text/css rel=stylesheet><LINK media=all 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Knuth's Algorithm X - Wikipedia, the free encyclopedia.files\index(3).css" 
type=text/css rel=stylesheet><LINK media=all 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Knuth's Algorithm X - Wikipedia, the free encyclopedia.files\index(4).css" 
type=text/css rel=stylesheet>
<SCRIPT type=text/javascript>
var skin="monobook",
stylepath="/skins-1.5",
wgArticlePath="/wiki/$1",
wgScriptPath="/w",
wgScriptExtension=".php",
wgScript="/w/index.php",
wgVariantArticlePath=false,
wgActionPaths={},
wgServer="http://en.wikipedia.org",
wgCanonicalNamespace="",
wgCanonicalSpecialPageName=false,
wgNamespaceNumber=0,
wgPageName="Knuth\'s_Algorithm_X",
wgTitle="Knuth\'s Algorithm X",
wgAction="view",
wgArticleId=3626542,
wgIsArticle=true,
wgUserName=null,
wgUserGroups=null,
wgUserLanguage="en",
wgContentLanguage="en",
wgBreakFrames=false,
wgCurRevisionId=297311604,
wgVersion="1.16alpha-wmf",
wgEnableAPI=true,
wgEnableWriteAPI=true,
wgSeparatorTransformTable=["", ""],
wgDigitTransformTable=["", ""],
wgMainPageTitle="Main Page",
wgFormattedNamespaces={"-2": "Media", "-1": "Special", "0": "", "1": "Talk", "2": "User", "3": "User talk", "4": "Wikipedia", "5": "Wikipedia talk", "6": "File", "7": "File talk", "8": "MediaWiki", "9": "MediaWiki talk", "10": "Template", "11": "Template talk", "12": "Help", "13": "Help talk", "14": "Category", "15": "Category talk", "100": "Portal", "101": "Portal talk"},
wgNamespaceIds={"media": -2, "special": -1, "": 0, "talk": 1, "user": 2, "user_talk": 3, "wikipedia": 4, "wikipedia_talk": 5, "file": 6, "file_talk": 7, "mediawiki": 8, "mediawiki_talk": 9, "template": 10, "template_talk": 11, "help": 12, "help_talk": 13, "category": 14, "category_talk": 15, "portal": 100, "portal_talk": 101, "wp": 4, "wt": 5, "image": 6, "image_talk": 7},
wgMWSuggestTemplate="http://en.wikipedia.org/w/api.php?action=opensearch\x26search={searchTerms}\x26namespace={namespaces}\x26suggest",
wgDBname="enwiki",
wgSearchNamespaces=[0],
wgMWSuggestMessages=["with suggestions", "no suggestions"],
wgRestrictionEdit=[],
wgRestrictionMove=[],
wgTrackingToken="353154cd36dc41398f0ed46672669eee",
wgClickTrackingIsThrottled=true,
wgNotice="",
wgNoticeLocal="";
</SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/wikibits.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/ajax.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/mwsuggest.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/js2.combined.min.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/plugins.combined.min.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/CollapsibleTabs.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/ClickTracking.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/centralnotice.js" 
type=text/javascript></SCRIPT>
<!--[if lt IE 7]>
<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/IEFixes.js" 
type=text/javascript></SCRIPT>

<META http-equiv=imagetoolbar content=no><![endif]-->
<SCRIPT 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/index.php" 
type=text/javascript></SCRIPT>
</HEAD>
<BODY 
class="mediawiki ltr ns-0 ns-subject page-Knuth_s_Algorithm_X skin-monobook">
<DIV id=globalWrapper>
<DIV id=column-content>
<DIV id=content><A id=top></A>
<DIV id=siteNotice>
<SCRIPT 
type=text/javascript>if (wgNotice != '') document.writeln(wgNotice);</SCRIPT>
</DIV>
<H1 class=firstHeading id=firstHeading>Knuth's Algorithm X</H1>
<DIV id=bodyContent>
<H3 id=siteSub>From Wikipedia, the free encyclopedia</H3>
<DIV id=contentSub>&nbsp;&nbsp;(Redirected from <A title="Algorithm X" 
href="http://en.wikipedia.org/w/index.php?title=Algorithm_X&amp;redirect=no">Algorithm 
X</A>)</DIV>
<DIV id=jump-to-nav>Jump to: <A 
href="http://en.wikipedia.org/wiki/Algorithm_X#column-one">navigation</A>, <A 
href="http://en.wikipedia.org/wiki/Algorithm_X#searchInput">search</A></DIV><!-- start content -->
<P><A title="Donald Knuth" 
href="http://en.wikipedia.org/wiki/Donald_Knuth">Donald Knuth</A>'s <B>Algorithm 
X</B> is a <A title="Recursion (computer science)" 
href="http://en.wikipedia.org/wiki/Recursion_(computer_science)">recursive</A>, 
<A title="Nondeterministic algorithm" 
href="http://en.wikipedia.org/wiki/Nondeterministic_algorithm">nondeterministic</A>, 
<A class=mw-redirect title=Depth-first 
href="http://en.wikipedia.org/wiki/Depth-first">depth-first</A>, <A 
title=Backtracking 
href="http://en.wikipedia.org/wiki/Backtracking">backtracking</A> <A 
title=Algorithm href="http://en.wikipedia.org/wiki/Algorithm">algorithm</A> that 
finds all solutions to the <A title="Exact cover" 
href="http://en.wikipedia.org/wiki/Exact_cover">exact cover</A> problem 
represented by a matrix <I>A</I> consisting of 0s and 1s. The goal is to select 
a subset of the rows so that the digit 1 appears in each column exactly 
once.</P>
<P>Algorithm X functions as follows:</P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TD>
        <OL>
          <LI>If the matrix <I>A</I> is empty, the problem is solved; terminate 
          successfully. 
          <LI>Otherwise choose a column <I>c</I> (<A 
          title="Deterministic algorithm" 
          href="http://en.wikipedia.org/wiki/Deterministic_algorithm">deterministically</A>). 

          <LI>Choose a row <I>r</I> such that <I>A</I><SUB><I>r</I>, 
          <I>c</I></SUB> = 1 (<A title="Nondeterministic algorithm" 
          href="http://en.wikipedia.org/wiki/Nondeterministic_algorithm">nondeterministically</A>). 

          <LI>Include row <I>r</I> in the partial solution. 
          <LI>For each column <I>j</I> such that <I>A</I><SUB><I>r</I>, 
          <I>j</I></SUB> = 1, 
          <DL>
            <DD>for each row <I>i</I> such that <I>A</I><SUB><I>i</I>, 
            <I>j</I></SUB> = 1, 
            <DL>
              <DD>delete row <I>i</I> from matrix <I>A</I>; </DD></DL>
            <DD>delete column <I>j</I> from matrix <I>A</I>. </DD></DL>
          <LI>Repeat this algorithm recursively on the reduced matrix <I>A</I>. 
          </LI></OL></TD></TR></TBODY></TABLE></DD></DL>
<P>The nondeterministic choice of <I>r</I> means that the algorithm essentially 
clones itself into independent subalgorithms; each subalgorithm inherits the 
current matrix <I>A</I>, but reduces it with respect to a different row 
<I>r</I>. If column <I>c</I> is entirely zero, there are no subalgorithms and 
the process terminates unsuccessfully.</P>
<P>The subalgorithms form a <A title="Search tree" 
href="http://en.wikipedia.org/wiki/Search_tree">search tree</A> in a natural 
way, with the original problem at the root and with level <I>k</I> containing 
each subalgorithm that corresponds to <I>k</I> chosen rows. Backtracking is the 
process of traversing the tree in preorder, depth first.</P>
<P>Any systematic rule for choosing column <I>c</I> in this procedure will find 
all solutions, but some rules work much better than others. To reduce the number 
of iterations, <A title="Donald Knuth" 
href="http://en.wikipedia.org/wiki/Donald_Knuth">Knuth</A> suggests that the 
column choosing algorithm select a column with the lowest number of 1s in 
it.</P>
<TABLE class=toc id=toc>
  <TBODY>
  <TR>
    <TD>
      <DIV id=toctitle>
      <H2>Contents</H2></DIV>
      <UL>
        <LI class="toclevel-1 tocsection-1"><A 
        href="http://en.wikipedia.org/wiki/Algorithm_X#Example"><SPAN 
        class=tocnumber>1</SPAN> <SPAN class=toctext>Example</SPAN></A> 
        <LI class="toclevel-1 tocsection-2"><A 
        href="http://en.wikipedia.org/wiki/Algorithm_X#Implementations"><SPAN 
        class=tocnumber>2</SPAN> <SPAN class=toctext>Implementations</SPAN></A> 
        <LI class="toclevel-1 tocsection-3"><A 
        href="http://en.wikipedia.org/wiki/Algorithm_X#See_also"><SPAN 
        class=tocnumber>3</SPAN> <SPAN class=toctext>See also</SPAN></A> 
        <LI class="toclevel-1 tocsection-4"><A 
        href="http://en.wikipedia.org/wiki/Algorithm_X#References"><SPAN 
        class=tocnumber>4</SPAN> <SPAN class=toctext>References</SPAN></A> 
      </LI></UL></TD></TR></TBODY></TABLE>
<SCRIPT type=text/javascript>
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } 
//]]>
</SCRIPT>

<H2><SPAN class=editsection>[<A title="Edit section: Example" 
href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit&amp;section=1">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Example>Example</SPAN></H2>
<P>For example, consider the exact cover problem specified by the universe 
<I>U</I> = {1, 2, 3, 4, 5, 6, 7} and the collection of sets <IMG class=tex 
alt=\mathcal{S} 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
= {<I>A</I>, <I>B</I>, <I>C</I>, <I>D</I>, <I>E</I>, <I>F</I>}, where:</P>
<DL>
  <DD>
  <UL>
    <LI><I>A</I> = {1, 4, 7}; 
    <LI><I>B</I> = {1, 4}; 
    <LI><I>C</I> = {4, 5, 7}; 
    <LI><I>D</I> = {3, 5, 6}; 
    <LI><I>E</I> = {2, 3, 6, 7}; and 
    <LI><I>F</I> = {2, 7}. </LI></UL></DD></DL>
<P>This problem is represented by the matrix:</P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TH></TH>
      <TH>1</TH>
      <TH>2</TH>
      <TH>3</TH>
      <TH>4</TH>
      <TH>5</TH>
      <TH>6</TH>
      <TH>7</TH></TR>
    <TR>
      <TH><I>A</I></TH>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><I>B</I></TH>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>C</I></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><I>D</I></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>E</I></TH>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><I>F</I></TH>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR></TBODY></TABLE></DD></DL>
<P>Algorithm X with Knuth's suggested heuristic for selecting columns solves 
this problem as follows:</P>
<P><B>Level 0</B></P>
<P>Step 1—The matrix is not empty, so the algorithm proceeds.</P>
<P>Step 2—The lowest number of 1s in any column is two. Column 1 is the first 
column with two 1s and thus is selected (deterministically):</P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TH></TH>
      <TH><SPAN style="COLOR: red">1</SPAN></TH>
      <TH>2</TH>
      <TH>3</TH>
      <TH>4</TH>
      <TH>5</TH>
      <TH>6</TH>
      <TH>7</TH></TR>
    <TR>
      <TH><I>A</I></TH>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><I>B</I></TH>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>C</I></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><I>D</I></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>E</I></TH>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><I>F</I></TH>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR></TBODY></TABLE></DD></DL>
<P>Step 3—Rows <I>A</I> and <I>B</I> each have a 1 in column 1 and thus are 
selected (nondeterministically).</P>
<P>The algorithm moves to the first branch at level 1…</P>
<DL>
  <DD><B>Level 1: Select Row <I>A</I></B> </DD></DL>
<DL>
  <DD>Step 4—Row <I>A</I> is included in the partial solution. </DD></DL>
<DL>
  <DD>Step 5—Row <I>A</I> has a 1 in columns 1, 4, and 7: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH><SPAN style="COLOR: blue">1</SPAN></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH><SPAN style="COLOR: blue">4</SPAN></TH>
        <TH>5</TH>
        <TH>6</TH>
        <TH><SPAN style="COLOR: blue">7</SPAN></TH></TR>
      <TR>
        <TH><SPAN style="COLOR: red"><I>A</I></SPAN></TH>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR>
      <TR>
        <TH><I>B</I></TH>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>C</I></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>E</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>F</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Column 1 has a 1 in rows <I>A</I> and <I>B</I>; column 4 has a 1 in rows 
  <I>A</I>, <I>B</I>, and <I>C</I>; and column 7 has a 1 in rows <I>A</I>, 
  <I>C</I>, <I>E</I>, and <I>F</I>. Thus rows <I>A</I>, <I>B</I>, <I>C</I>, 
  <I>E</I>, and <I>F</I> are to be removed and columns 1, 4 and 7 are to be 
  removed: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH><SPAN style="COLOR: red">1</SPAN></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH><SPAN style="COLOR: red">4</SPAN></TH>
        <TH>5</TH>
        <TH>6</TH>
        <TH><SPAN style="COLOR: red">7</SPAN></TH></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>A</I></SPAN></TH>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>B</I></SPAN></TH>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>C</I></SPAN></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>E</I></SPAN></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>F</I></SPAN></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN 
    style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Row <I>D</I> remains and columns 2, 3, 5, and 6 remain: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH>5</TH>
        <TH>6</TH></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Step 1—The matrix is not empty, so the algorithm proceeds. </DD></DL>
<DL>
  <DD>Step 2—The lowest number of 1s in any column is zero and column 2 is the 
  first column with zero 1s: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH><SPAN style="COLOR: red">2</SPAN></TH>
        <TH>3</TH>
        <TH>5</TH>
        <TH>6</TH></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Thus this branch of the algorithm terminates unsuccessfully. </DD></DL>
<DL>
  <DD>The algorithm moves to the next branch at level 1… </DD></DL>
<DL>
  <DD><B>Level 1: Select Row <I>B</I></B> </DD></DL>
<DL>
  <DD>Step 4—Row <I>B</I> is included in the partial solution. </DD></DL>
<DL>
  <DD>Row <I>B</I> has a 1 in columns 1 and 4: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH><SPAN style="COLOR: blue">1</SPAN></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH><SPAN style="COLOR: blue">4</SPAN></TH>
        <TH>5</TH>
        <TH>6</TH>
        <TH>7</TH></TR>
      <TR>
        <TH><I>A</I></TH>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><SPAN style="COLOR: red"><I>B</I></SPAN></TH>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>C</I></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>E</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>F</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Column 1 has a 1 in rows <I>A</I> and <I>B</I>; and column 4 has a 1 in 
  rows <I>A</I>, <I>B</I>, and <I>C</I>. Thus rows <I>A</I>, <I>B</I>, and 
  <I>C</I> are to be removed and columns 1 and 4 are to be removed: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH><SPAN style="COLOR: red">1</SPAN></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH><SPAN style="COLOR: red">4</SPAN></TH>
        <TH>5</TH>
        <TH>6</TH>
        <TH>7</TH></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>A</I></SPAN></TH>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>B</I></SPAN></TH>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><SPAN style="COLOR: blue"><I>C</I></SPAN></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>E</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>F</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Rows <I>D</I>, <I>E</I>, and <I>F</I> remain and columns 2, 3, 5, 6, and 7 
  remain: </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH>5</TH>
        <TH>6</TH>
        <TH>7</TH></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>E</I></TH>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>F</I></TH>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Step 1—The matrix is not empty, so the algorithm proceeds. </DD></DL>
<DL>
  <DD>Step 2—The lowest number of 1s in any column is one. Column 5 is the first 
  column with one 1 and thus is selected (deterministically): </DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <TABLE cellSpacing=0 cellPadding=5 border=1>
      <TBODY>
      <TR>
        <TH></TH>
        <TH>2</TH>
        <TH>3</TH>
        <TH><SPAN style="COLOR: red">5</SPAN></TH>
        <TH>6</TH>
        <TH>7</TH></TR>
      <TR>
        <TH><I>D</I></TH>
        <TD>0</TD>
        <TD>1</TD>
        <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
        <TD>1</TD>
        <TD>0</TD></TR>
      <TR>
        <TH><I>E</I></TH>
        <TD>1</TD>
        <TD>1</TD>
        <TD>0</TD>
        <TD>1</TD>
        <TD>1</TD></TR>
      <TR>
        <TH><I>F</I></TH>
        <TD>1</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>0</TD>
        <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL>
<DL>
  <DD>Step 3—Row <I>D</I> has a 1 in column 5 and thus is selected 
  (nondeterministically). </DD></DL>
<DL>
  <DD>The algorithm moves to the first branch at level 2… </DD></DL>
<DL>
  <DD>
  <DL>
    <DD><B>Level 2: Select Row <I>D</I></B> </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Step 4—Row <I>D</I> is included in the partial solution. 
</DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Step 5—Row <I>D</I> has a 1 in columns 3, 5, and 6: </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>
      <TABLE cellSpacing=0 cellPadding=5 border=1>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>2</TH>
          <TH><SPAN style="COLOR: blue">3</SPAN></TH>
          <TH><SPAN style="COLOR: blue">5</SPAN></TH>
          <TH><SPAN style="COLOR: blue">6</SPAN></TH>
          <TH>7</TH></TR>
        <TR>
          <TH><SPAN style="COLOR: red"><I>D</I></SPAN></TH>
          <TD>0</TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD>0</TD></TR>
        <TR>
          <TH><I>E</I></TH>
          <TD>1</TD>
          <TD>1</TD>
          <TD>0</TD>
          <TD>1</TD>
          <TD>1</TD></TR>
        <TR>
          <TH><I>F</I></TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>0</TD>
          <TD>0</TD>
          <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Column 3 has a 1 in rows <I>D</I> and <I>E</I>; column 5 has a 1 in row 
    <I>D</I>; and column 6 has a 1 in rows <I>D</I> and <I>E</I>. Thus rows 
    <I>D</I> and <I>E</I> are to be removed and columns 3, 5, and 6 are to be 
    removed: </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>
      <TABLE cellSpacing=0 cellPadding=5 border=1>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>2</TH>
          <TH><SPAN style="COLOR: red">3</SPAN></TH>
          <TH><SPAN style="COLOR: red">5</SPAN></TH>
          <TH><SPAN style="COLOR: red">6</SPAN></TH>
          <TH>7</TH></TR>
        <TR>
          <TH><SPAN style="COLOR: blue"><I>D</I></SPAN></TH>
          <TD>0</TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD>0</TD></TR>
        <TR>
          <TH><SPAN style="COLOR: blue"><I>E</I></SPAN></TH>
          <TD>1</TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD>0</TD>
          <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
          <TD>1</TD></TR>
        <TR>
          <TH><I>F</I></TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>0</TD>
          <TD>0</TD>
          <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Row <I>F</I> remains and columns 2 and 7 remain: </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>
      <TABLE cellSpacing=0 cellPadding=5 border=1>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>2</TH>
          <TH>7</TH></TR>
        <TR>
          <TH><I>F</I></TH>
          <TD>1</TD>
          <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Step 1—The matrix is not empty, so the algorithm proceeds. 
</DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Step 2—The lowest number of 1s in any column is one. Column 2 is the 
    first column with one 1 and thus is selected (deterministically). 
  </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>Row <I>F</I> has a 1 in column 2 and thus is selected 
    (nondeterministically). </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>The algorithm moves to the first branch at level 3… </DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD><B>Level 3: Select Row <I>F</I></B> </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>Step 4—Row <I>F</I> is included in the partial solution. 
  </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>Row <I>F</I> has a 1 in columns 2 and 7: </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>
      <DL>
        <DD>
        <TABLE cellSpacing=0 cellPadding=5 border=1>
          <TBODY>
          <TR>
            <TH></TH>
            <TH><SPAN style="COLOR: blue">2</SPAN></TH>
            <TH><SPAN style="COLOR: blue">7</SPAN></TH></TR>
          <TR>
            <TH><SPAN style="COLOR: red"><I>F</I></SPAN></TH>
            <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
            <TD><SPAN 
          style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR></TBODY></TABLE></DD></DL></DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>Column 2 has a 1 in row <I>F</I>; and column 7 has a 1 in row 
      <I>F</I>. Thus row <I>F</I> is to be removed and columns 2 and 7 are to be 
      removed: </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>
      <DL>
        <DD>
        <TABLE cellSpacing=0 cellPadding=5 border=1>
          <TBODY>
          <TR>
            <TH></TH>
            <TH><SPAN style="COLOR: red">2</SPAN></TH>
            <TH><SPAN style="COLOR: red">7</SPAN></TH></TR>
          <TR>
            <TH><SPAN style="COLOR: blue"><I>F</I></SPAN></TH>
            <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
            <TD><SPAN 
          style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR></TBODY></TABLE></DD></DL></DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>Step 1—The matrix is empty, thus this branch of the algorithm 
      terminates successfully. </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>As rows <I>B</I>, <I>D</I>, and <I>F</I> are selected, the final 
      solution is: </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>
      <DL>
        <DD>
        <TABLE cellSpacing=0 cellPadding=5 border=1>
          <TBODY>
          <TR>
            <TH></TH>
            <TH>1</TH>
            <TH>2</TH>
            <TH>3</TH>
            <TH>4</TH>
            <TH>5</TH>
            <TH>6</TH>
            <TH>7</TH></TR>
          <TR>
            <TH><I>B</I></TH>
            <TD>1</TD>
            <TD>0</TD>
            <TD>0</TD>
            <TD>1</TD>
            <TD>0</TD>
            <TD>0</TD>
            <TD>0</TD></TR>
          <TR>
            <TH><I>D</I></TH>
            <TD>0</TD>
            <TD>0</TD>
            <TD>1</TD>
            <TD>0</TD>
            <TD>1</TD>
            <TD>1</TD>
            <TD>0</TD></TR>
          <TR>
            <TH><I>F</I></TH>
            <TD>0</TD>
            <TD>1</TD>
            <TD>0</TD>
            <TD>0</TD>
            <TD>0</TD>
            <TD>0</TD>
            <TD>1</TD></TR></TBODY></TABLE></DD></DL></DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>In other words, the subcollection {<I>B</I>, <I>D</I>, <I>F</I>} is an 
      exact cover, since every element is contained in exactly one of the sets 
      <I>B</I> = {1, 4}, <I>D</I> = {3, 5, 6}, or <I>F</I> = {2, 7}. 
    </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>
    <DL>
      <DD>There are no more selected rows at level 3, thus the algorithm moves 
      to the next branch at level 2… </DD></DL></DD></DL></DD></DL>
<DL>
  <DD>
  <DL>
    <DD>There are no more selected rows at level 2, thus the algorithm moves to 
    the next branch at level 1… </DD></DL></DD></DL>
<DL>
  <DD>There are no more selected rows at level 1, thus the algorithm moves to 
  the next branch at level 0… </DD></DL>
<P>There are no branches at level 0, thus the algorithm terminates.</P>
<P>In summary, the algorithm determines there is only one exact cover: <IMG 
class=tex alt=\mathcal{S}^* 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>}.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Implementations" 
href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit&amp;section=2">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Implementations>Implementations</SPAN></H2>
<P><A title="Dancing Links" 
href="http://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</A>, commonly 
known as DLX, is the technique suggested by <A title="Donald Knuth" 
href="http://en.wikipedia.org/wiki/Donald_Knuth">Knuth</A> to efficiently 
implement his Algorithm X on a computer. Dancing Links implements the matrix 
using circular <A class=mw-redirect title="Doubly linked list" 
href="http://en.wikipedia.org/wiki/Doubly_linked_list">doubly-linked lists</A> 
of the 1s in the matrix. There is a list of 1s for each row and each column. 
Each 1 in the matrix has a link to the next 1 above, below, to the left, and to 
the right of itself.</P>
<H2><SPAN class=editsection>[<A title="Edit section: See also" 
href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit&amp;section=3">edit</A>]</SPAN> 
<SPAN class=mw-headline id=See_also>See also</SPAN></H2>
<UL>
  <LI><A title="Exact cover" 
  href="http://en.wikipedia.org/wiki/Exact_cover">Exact cover</A> 
  <LI><A title="Dancing Links" 
  href="http://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</A> </LI></UL>
<H2><SPAN class=editsection>[<A title="Edit section: References" 
href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit&amp;section=4">edit</A>]</SPAN> 
<SPAN class=mw-headline id=References>References</SPAN></H2>
<UL>
  <LI><SPAN class=citation id=CITEREFKnuth2000><A title="Donald Knuth" 
  href="http://en.wikipedia.org/wiki/Donald_Knuth">Knuth, Donald E.</A> (2000), 
  "Dancing links", in Davies, Jim; Roscoe, Bill; Woodcock, Jim, <I>Millennial 
  Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft 
  Symposium in Honour of Sir Tony Hoare</I>, Palgrave, pp.&nbsp;187–214, <A 
  title=ArXiv href="http://en.wikipedia.org/wiki/ArXiv">arΧiv</A>:<A class=extiw 
  title=arxiv:cs/0011047 href="http://arxiv.org/abs/cs/0011047">cs/0011047</A>, 
  <A title="International Standard Book Number" 
  href="http://en.wikipedia.org/wiki/International_Standard_Book_Number">ISBN</A> 
  <A title=Special:BookSources/9780333922309 
  href="http://en.wikipedia.org/wiki/Special:BookSources/9780333922309">9780333922309</A></SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=bookitem&amp;rft.btitle=Dancing+links&amp;rft.atitle=Millennial+Perspectives+in+Computer+Science%3A+Proceedings+of+the+1999+Oxford-Microsoft+Symposium+in+Honour+of+Sir+Tony+Hoare&amp;rft.aulast=Knuth&amp;rft.aufirst=Donald+E.&amp;rft.au=Knuth%2C%26%2332%3BDonald+E.&amp;rft.date=2000&amp;rft.pages=pp.%26nbsp%3B187%E2%80%93214&amp;rft.pub=Palgrave&amp;rft.isbn=9780333922309&amp;rfr_id=info:sid/en.wikipedia.org:Knuth%27s_Algorithm_X><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN>. </LI></UL><!-- 
NewPP limit report
Preprocessor node count: 837/1000000
Post-expand include size: 6153/2048000 bytes
Template argument size: 1738/2048000 bytes
Expensive parser function count: 0/500
--><!-- Saved in parser cache with key enwiki:pcache:idhash:3626542-0!1!0!default!!en!2 and timestamp 20091216053702 -->
<DIV class=printfooter>Retrieved from "<A 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">http://en.wikipedia.org/wiki/Knuth's_Algorithm_X</A>"</DIV>
<DIV class=catlinks id=catlinks>
<DIV id=mw-normal-catlinks><A title=Special:Categories 
href="http://en.wikipedia.org/wiki/Special:Categories">Categories</A>: <SPAN 
dir=ltr><A title="Category:Search algorithms" 
href="http://en.wikipedia.org/wiki/Category:Search_algorithms">Search 
algorithms</A></SPAN> | <SPAN dir=ltr><A title="Category:Donald Knuth" 
href="http://en.wikipedia.org/wiki/Category:Donald_Knuth">Donald 
Knuth</A></SPAN></DIV></DIV><!-- end content -->
<DIV class=visualClear></DIV></DIV></DIV></DIV>
<DIV id=column-one>
<DIV class=portlet id=p-cactions>
<H5>Views</H5>
<DIV class=pBody>
<UL lang=en xml:lang="en">
  <LI class=selected id=ca-nstab-main><A title="View the content page [c]" 
  accessKey=c 
  href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Article</A> 
  <LI id=ca-talk><A title="Discussion about the content page [t]" accessKey=t 
  href="http://en.wikipedia.org/wiki/Talk:Knuth's_Algorithm_X">Discussion</A> 
  <LI id=ca-edit><A 
  title="You can edit this page. &#10;Please use the preview button before saving. [e]" 
  accessKey=e 
  href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=edit">Edit 
  this page</A> 
  <LI id=ca-history><A title="Past versions of this page [h]" accessKey=h 
  href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;action=history">History</A> 
  </LI></UL></DIV></DIV>
<DIV class=portlet id=p-personal>
<H5>Personal tools</H5>
<DIV class=pBody>
<UL lang=en xml:lang="en">
  <LI id=pt-optin-try><A class=no-text-transform title="Try out new features" 
  href="http://en.wikipedia.org/w/index.php?title=Special:UsabilityInitiativeOptIn&amp;from=Knuth%27s_Algorithm_X">Try 
  Beta</A> 
  <LI id=pt-login><A 
  title="You are encouraged to log in; however, it is not mandatory. [o]" 
  accessKey=o 
  href="http://en.wikipedia.org/w/index.php?title=Special:UserLogin&amp;returnto=Knuth%27s_Algorithm_X">Log 
  in / create account</A> </LI></UL></DIV></DIV>
<DIV class=portlet id=p-logo><A title="Visit the main page" 
style="BACKGROUND-IMAGE: url(http://upload.wikimedia.org/wikipedia/en/b/bc/Wiki.png)" 
href="http://en.wikipedia.org/wiki/Main_Page"></A></DIV>
<SCRIPT type=text/javascript> if (window.isMSIE55) fixalpha(); </SCRIPT>

<DIV class="generated-sidebar portlet" id=p-navigation>
<H5 lang=en xml:lang="en">Navigation</H5>
<DIV class=pBody>
<UL>
  <LI id=n-mainpage-description><A title="Visit the main page [z]" accessKey=z 
  href="http://en.wikipedia.org/wiki/Main_Page">Main page</A> 
  <LI id=n-contents><A title="Guides to browsing Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Contents">Contents</A> 
  <LI id=n-featuredcontent><A title="Featured content — the best of Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Featured_content">Featured 
  content</A> 
  <LI id=n-currentevents><A 
  title="Find background information on current events" 
  href="http://en.wikipedia.org/wiki/Portal:Current_events">Current events</A> 
  <LI id=n-randompage><A title="Load a random article [x]" accessKey=x 
  href="http://en.wikipedia.org/wiki/Special:Random">Random article</A> 
</LI></UL></DIV></DIV>
<DIV class=portlet id=p-search>
<H5 lang=en xml:lang="en"><LABEL for=searchInput>Search</LABEL></H5>
<DIV class=pBody id=searchBody>
<FORM id=searchform action=/w/index.php><INPUT type=hidden value=Special:Search 
name=title> <INPUT id=searchInput title="Search Wikipedia" accessKey=f 
name=search> <INPUT class=searchButton id=searchGoButton title="Go to a page with this exact name if one exists" type=submit value=Go name=go>&nbsp; 
<INPUT class=searchButton id=mw-searchButton title="Search Wikipedia for this text" type=submit value=Search name=fulltext> 
</FORM></DIV></DIV>
<DIV class="generated-sidebar portlet" id=p-interaction>
<H5 lang=en xml:lang="en">Interaction</H5>
<DIV class=pBody>
<UL>
  <LI id=n-aboutsite><A title="Find out about Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> 
  <LI id=n-portal><A 
  title="About the project, what you can do, where to find things" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Community_portal">Community 
  portal</A> 
  <LI id=n-recentchanges><A title="The list of recent changes in the wiki [r]" 
  accessKey=r href="http://en.wikipedia.org/wiki/Special:RecentChanges">Recent 
  changes</A> 
  <LI id=n-contact><A title="How to contact Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</A> 

  <LI id=n-sitesupport><A title="Support us" 
  href="http://wikimediafoundation.org/wiki/Support_Wikipedia/en">Donate to 
  Wikipedia</A> 
  <LI id=n-help><A title="Guidance on how to use and edit Wikipedia" 
  href="http://en.wikipedia.org/wiki/Help:Contents">Help</A> 
</LI></UL></DIV></DIV>
<DIV class=portlet id=p-tb>
<H5 lang=en xml:lang="en">Toolbox</H5>
<DIV class=pBody>
<UL>
  <LI id=t-whatlinkshere><A 
  title="List of all English Wikipedia pages containing links to this page [j]" 
  accessKey=j 
  href="http://en.wikipedia.org/wiki/Special:WhatLinksHere/Knuth's_Algorithm_X">What 
  links here</A> 
  <LI id=t-recentchangeslinked><A 
  title="Recent changes in pages linked from this page [k]" accessKey=k 
  href="http://en.wikipedia.org/wiki/Special:RecentChangesLinked/Knuth's_Algorithm_X">Related 
  changes</A> 
  <LI id=t-upload><A title="Upload files [u]" accessKey=u 
  href="http://en.wikipedia.org/wiki/Wikipedia:Upload">Upload file</A> 
  <LI id=t-specialpages><A title="List of all special pages [q]" accessKey=q 
  href="http://en.wikipedia.org/wiki/Special:SpecialPages">Special pages</A> 
  <LI id=t-print><A title="Printable version of this page [p]" accessKey=p 
  href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;printable=yes" 
  rel=alternate>Printable version</A> 
  <LI id=t-permalink><A title="Permanent link to this revision of the page" 
  href="http://en.wikipedia.org/w/index.php?title=Knuth%27s_Algorithm_X&amp;oldid=297311604">Permanent 
  link</A>
  <LI id=t-cite><A title="Information on how to cite this page" 
  href="http://en.wikipedia.org/w/index.php?title=Special:Cite&amp;page=Knuth%27s_Algorithm_X&amp;id=297311604">Cite 
  this page</A> </LI></UL></DIV></DIV></DIV><!-- end of the left (by default at least) column -->
<DIV class=visualClear></DIV>
<DIV id=footer>
<DIV id=f-poweredbyico><A href="http://www.mediawiki.org/"><IMG height=31 
alt="Powered by MediaWiki" 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/poweredby_mediawiki_88x31.png" 
width=88></A></DIV>
<DIV id=f-copyrightico><A href="http://wikimediafoundation.org/"><IMG height=31 
alt="Wikimedia Foundation" 
src="Knuth's Algorithm X - Wikipedia, the free encyclopedia.files/wikimedia-button.png" 
width=88></A></DIV>
<UL id=f-list>
  <LI id=lastmod>This page was last modified on 19 June 2009 at 06:24. 
  <LI id=copyright>Text is available under the <A 
  href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License" 
  rel=license>Creative Commons Attribution-ShareAlike License</A><A 
  style="DISPLAY: none" href="http://creativecommons.org/licenses/by-sa/3.0/" 
  rel=license></A>; additional terms may apply. See <A 
  href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</A> for 
  details.<BR>Wikipedia® is a registered trademark of the <A 
  href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</A>, a 
  non-profit organization.
  <LI><A class=internal 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</A> 
  <LI id=privacy><A title="wikimedia:Privacy policy" 
  href="http://wikimediafoundation.org/wiki/Privacy_policy">Privacy policy</A> 
  <LI id=about><A title=Wikipedia:About 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> 
  <LI id=disclaimer><A title="Wikipedia:General disclaimer" 
  href="http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer">Disclaimers</A> 
  </LI></UL></DIV></DIV>
<SCRIPT type=text/javascript>if (window.runOnloadHook) runOnloadHook();</SCRIPT>
<!-- Served by srv212 in 0.075 secs. --></BODY></HTML>
